#include "cursor.h"
#include <stdlib.h>
#include "fatal.h"

/* Place in the interface file */
struct Node
{
    ElementType Element;
    Position    Next;
};

struct Node CursorSpace[ SpaceSize ];

/* START: fig3_31.txt */
static Position
CursorAlloc( void )
{
    Position P;

    P = CursorSpace[ 0 ].Next;
    CursorSpace[ 0 ].Next = CursorSpace[ P ].Next;

    return P;
}

static void
CursorFree( Position P )
{
    CursorSpace[ P ].Next = CursorSpace[ 0 ].Next;
    CursorSpace[ 0 ].Next = P;
}
/* END */

void
InitializeCursorSpace( void )
{
    int i;

    for( i = 0; i < SpaceSize; i++ )
        CursorSpace[ i ].Next = i + 1;
    CursorSpace[ SpaceSize - 1 ].Next = 0;
}

List
MakeEmpty( List L )
{
    if( L != NULL )
        DeleteList( L );
    L = CursorAlloc( );
    if( L == 0 )
        FatalError( "Out of memory!" );
    CursorSpace[ L ].Next = 0;
    return L;
}

/* START: fig3_32.txt */
/* Return true if L is empty */

int
IsEmpty( List L )
{
    return CursorSpace[ L ].Next == 0;
}
/* END */

/* START: fig3_33.txt */
/* Return true if P is the last position in list L */
/* Parameter L is unused in this implementation */

int IsLast( Position P, List L )
{
    return CursorSpace[ P ].Next == 0;
}
/* END */

/* START: fig3_34.txt */
        /* Return Position of X in L; 0 if not found */
        /* Uses a header node */

        Position
        Find( ElementType X, List L )
        {
            Position P;

/* 1*/      P = CursorSpace[ L ].Next;
/* 2*/      while( P && CursorSpace[ P ].Element != X )
/* 3*/          P = CursorSpace[ P ].Next;

/* 4*/      return P;
        }
/* END */

/* START: fig3_35.txt */
/* Delete from a list */
/* Assume that the position is legal */
/* Assume use of a header node */

void
Delete( ElementType X, List L )
{
    Position P, TmpCell;

    P = FindPrevious( X, L );

    if( !IsLast( P, L ) )  /* Assumption of header use */
    {                      /* X is found; delete it */
        TmpCell = CursorSpace[ P ].Next;
        CursorSpace[ P ].Next = CursorSpace[ TmpCell ].Next;
        CursorFree( TmpCell );
    }
}
/* END */

        /* If X is not found, then Next field of returned value is 0 */
        /* Assumes a header */

        Position
        FindPrevious( ElementType X, List L )
        {
            Position P;

/* 1*/      P = L;
/* 2*/      while( CursorSpace[ P ].Next &&
                    CursorSpace[ CursorSpace[ P ].Next ].Element != X )
/* 3*/          P = CursorSpace[ P ].Next;

/* 4*/      return P;
        }

/* START: fig3_36.txt */
        /* Insert (after legal position P) */
        /* Header implementation assumed */
        /* Parameter L is unused in this implementation */

        void
        Insert( ElementType X, List L, Position P )
        {
            Position TmpCell;

/* 1*/      TmpCell = CursorAlloc( );
/* 2*/      if( TmpCell == 0 )
/* 3*/          FatalError( "Out of space!!!" );

/* 4*/      CursorSpace[ TmpCell ].Element = X;
/* 5*/      CursorSpace[ TmpCell ].Next = CursorSpace[ P ].Next;
/* 6*/      CursorSpace[ P ].Next = TmpCell;
        }
/* END */


        /* Correct DeleteList algorithm */

        void
        DeleteList( List L )
        {
            Position P, Tmp;

/* 1*/      P = CursorSpace[ L ].Next;  /* Header assumed */
/* 2*/      CursorSpace[ L ].Next = 0;
/* 3*/      while( P != 0 )
            {
/* 4*/          Tmp = CursorSpace[ P ].Next;
/* 5*/          CursorFree( P );
/* 6*/          P = Tmp;
            }
        }

Position
Header( List L )
{
    return L;
}

Position
First( List L )
{
    return CursorSpace[ L ].Next;
}

Position
Advance( Position P )
{
    return CursorSpace[ P ].Next;
}

ElementType
Retrieve( Position P )
{
    return CursorSpace[ P ].Element;
}
